COMP124

Process Scheduling

Processor manager uses scheduling algorithms to despatch processes

• Looks at all processes in ready state
• Decides which to despatch
• Good algorithm will give impression of speed and responsiveness

Non-pre-emptive scheduling:

• Process stays on CPU until it terminates or blocks
• Implements multiprogramming
• Problems with compute-bound and I/O-bound processes
  Pre-emptive scheduling:
• Process can be interrupted and replaced with another process
• Implements multitasking

The burst time of a process -> time taken on the CPU before it blocks/terminates
The arrival time of a process -> time a process is first put into the ready state
The turnaround time is the time when a process terminated minus the time when it arrived in the process queue
The wait time is a process' turnaround time minus its burst time

Scheduling Policies

OS will have a policy according to some criteria

• Maximise throughput - Complete as many processes as possible in a given period
• Minimise turnaround time - Execute entire process as quickly as possible
• Minimise waiting time - Reduce time processes spend in ready state
• Maximise CPU efficiency - Keep CPU busy at all times
• Minimise latency - Reduce time taken between request and response
  Its impossible to meet every criteria all the time, so some will conflict
  Processor manager tried to ensure fairness to all processes
• Gives each process an equal amount of CPU and I/O time
• Ensure processes don't hog the CPU

Scheduling Algorithms

• First come first served (FCFS)
• Shortest job first (SJF)
• Shortest remaining time first (SRTF)
• Priority scheduling
• Round robin scheduling

First Come First Served

Easiest algorithm to implement and understand
Non-pre-emptive algorithm that deals with processes according to their arrival time

• Uses a FIFO queue to store ready processes
• Processes on the CPU stay until they terminate or block, then the next in queue get the CPU
  When a new process is created, its PCB is added to the back of the ready queue
  When CPU becomes free, process at the front of the queue is despatched:
• Its PCB restored to CPU
• Instruction pointer restored as part of this context switch

Lets say, three processes came in this order, with their respective burst times:
P1 -> 13ms
P2 -> 5ms
P3 -> 1ms

![[Pasted image 20250516103739.png]]
This process schedule can be shown as a Gantt chart, showing cumulative execution time
Average wait time can be calculated

• Find how long each process had to wait
  • P1 waited 0ms
  • P2 waited 13ms
  • P3 waited 18ms
• Average wait time = (0+13+18)/3=10.3ms

Order of arrival can have a dramatic effect on average wait time
For example, if the same processes arrived in the order:

• P2 -> 5ms
• P3 -> 1ms
• P1 -> 13ms
  Average wait time = (0+5+6)/3 = 3.7ms
  This is much lower because the biggest process arrived last

Advantages

• Very simple to implement as FIFO queue
• Scheduling overhead is minimal during context switch
• No starvation of processes

Disadvantages

• Throughput can be low due to long processes staying on CPU
• Average wait time is not minimal and can vary substantially
• Turnaround time and latency are hard to predict
• No ability to prioritise processes

Better performance could be achieved if schedule could be ordered so that large processes always go last

Shortest Job First

Non-pre-emptive algorithm that deals with processes according to their burst time

• When CPU is free, scheduler chooses process with shortest burst time
• If two processes have same burst time, choose according to arrival time
• Processes stay on CPU until terminated or blocked

For example, no matter the arrival time, if the ready processes and burst times are for example:

• P1 -> 5ms
• P2 -> 9ms
• P3 -> 6ms
• P4 -> 3ms
  They will be scheduled in the order: P4, P1, P3, P2
  This minimises the average wait time as short jobs are scheduled first

Advantages

• Reduces overall average wait time
• Provably optimal in giving minimal average wait time for a given set of processes

Disadvantages

• Can lead to process starvation
• Difficult to estimate burst times for new processes (often relies on prior history)

In general, non-pre-emptive algorithms are not suitable in modern OSs

• Many processes will be in the ready state
• All need fair access to the CPU
• Large processes would hog the CPU and reduce overall system performance
• The OS itself also has many processes that need time on the CPU

Shortest Remaining Time First

Processes are being created all the time

• The ready state is not a fixed set of processes
• New processes will appear and impact scheduling algorithm
  SRTF is a pre-emptive version of SJF
• CPU allocated to process that is closest to finishing
• If a new process arrives that is shorter than current running process, interrupt it
• Difficult to draw Gantt chart for pre-emptive algorithms
  The OS can only make a best guess about burst times and remaining times
• Can be based on previous performance and estimates
• Won't always be accurate

Advantages

• Short processes are handled very quickly
• Gives maximum throughput in most situations
• Requires little overhead during context switch

Disadvantages

• Starvation still possible
• Introduces extra context switches
• Waiting time and latency increase for longer processes

A better approach is to use a pre-emptive scheduling algorithm with a fixed time slice

• Implement multitasking with a fixed quantum and clock interrupts
• Scheduling algorithm still needs to decide which process to despatch next

Priority Scheduling

A pre-emptive algorithm that gives preferential treatment to important processes

• Each process has a priority assigned to it
• Highest priority in read queue gets onto the CPU first
• Processes with equal priority use FCFS
• If a new process arrives with higher priority than current process, interrupt it

Priorities can be set by the user or assigned by the OS depending on whatever characteristic is most important

• Memory usage
• I/O throughput
• Total CPU time
• Time elapsed

Let's say we have 5 processes in the ready queue:

• Process -> Burst (ms) -> Priority
• P1 -> 9 -> 3
• P2 -> 2 -> 2
• P3 -> 1 -> 5
• P4 -> 5 -> 3
• P5 -> 6 -> 4

Higher numbers mean higher priority (0 is least important)
These processes would be scheduled as follows:
![[Pasted image 20250516105746.png]]
Note that even though P1 and P4 both had priority 3, P1 came first as it was queued earlier

Average wait time

• P1 waited 7ms
• P2 waited 21ms
• P3 waited 0ms
• P4 waited 16ms
• P5 waited 1ms
  Average wait time = (7+21+0+16+1)/5 = 9ms

Advantages

• Smaller wait times and latency for higher priority processes
• Important processes are dealt with quickly

Disadvantages

• Bigger wait times and latency for lower priority processes
• Process starvation still possible

Commonly used in real-time OSs where processes must meet deadlines

Starvation can be solved by process aging

• Increase priority for processes that have been waiting for a long time
• Eventually their priority will bring them to the front of the queue

Round Robin Scheduling

A pre-emptive algorithm that gives a set amount of CPU time to each process
Time slice (quantum) is typically between 10ms and 100ms depending on OS and need

Similar to FCFS but processes can be interrupted before they terminate or block

Ready state is treated as a circular FIFO queue

• New processes arrive at back of queue
• Scheduler takes next process from front of queue
• Process runs for fixed amount of time
• Context switch moves current process to back of queue and despatches next in line
• Scheduler keeps going round and round all processes in the ready queue

When a process is placed onto the CPU, it will either

• Terminate before quantum expires
• Be interrupted (pre-empted) before it terminates

If the burst time is less than the quantum time:

• Process will terminate or block for I/O
• Scheduler will take next process from queue and place on CPU
• (See T (terminate) in Gantt chart)
  If the burst time is more than the quantum time:
• Process will be interrupted and a context switch will happen
• Interrupted process will be moved to the back of the ready queue
• (See P (pre-emptive) in Gantt chart)

For example, with the processes:

• P1 -> 14ms
• P2 -> 2ms
• P3 -> 5ms
• P4 -> 4ms
• P5 -> 9ms
  And the scheduler using a fixed time quantum of 4ms
  ![[Pasted image 20250516111227.png]]
  In this example:
• P1 had 4ms on CPU and was pre-empted
• P2 only needed 2ms and terminated before the quantum
• P3 had the next 4ms and was pre-empted
• P4 needed 4ms so used all the quantum before terminating
• P5 had the next 4ms and was pre-empted
  Then the round robin started again at the front of the queue

In the example, assume all processes arrived at time 0
Consider P2:

• It arrived at time 0 and terminated at time 6
• So its turnaround time was 6ms
• Its burst time was 2ms
• So its wait time was 4ms

Average turnaround time is

• (34+6+23+14+32)/5 = 21.8ms
  Average wait time is
• (20+4+18+10+23)/5 = 15ms

Advantages

• Easy to implement as a queue
• Doesn't depend on guessing or estimating burst times
• Response time based on number of processes instead of process burst times
• No starvation
• Balanced throughput

Disadvantages

• Depends on selecting a good time quantum
• Extensive overhead if quantum is too short

If quantum is too big, behaves like FCFS (but shorter processes executed faster)
If quantum is too small, behaves like SJF (but longer processes executed faster)

Windows Priority Scheduling Algorithm

Windows uses the Priority Round Robin algorithm
Priority values range from 0 to 31
Every new process is given one of five base priorities

• IDLE (4)
• BELOW_NORMAL (6)
• NORMAL (8) - The default priority
• HIGH (13)
• REALTIME (24)
  Processes given a priority boost when they are in the foreground
  Process can be boosted when it receives input or an event for which it has been waiting
  Boosted processes are reduced in priority by one level at the end of each quantum until base level is reached

Linux Priority Scheduling Algorithm

Linus also assigns a priority to each process

• Kernel processes have a value from 1 to 99
• User processes have a value from 100 to 139
  It also assigns a 'nice' value to each user
• Ranges from -20 (highest priority) to 19 (lowest priority)
• Default is 0 for every user
• Users can change priorities with nice and renice commands

Linux uses an algorithm called Completely Fair Scheduling (similar to Round Robin)

• Ready processes are stored in a balanced tree (not a queue)
• Gives credit for time spent in blocked state
• Time quantum varies depending on processor demand
• Process priority and nice values combine to give overall priority